package com.zll.study.排列组合;

import java.util.*;

/**
 * 有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合
 *
 * 示例1:
 *
 * 输入：S = “qqe”
 * 输出：[“eqq”,“qeq”,“qqe”]
 *
 * 示例2:
 *
 * 输入：S = “ab”
 * 输出：[“ab”, “ba”]
 *
 * 提示:
 *
 * 字符都是英文字母。
 * 字符串长度在[1, 9]之间
 */
public class leetcode面试题0808有重复字符串的排列组合 {
    public static void main(String[] args) {
        String input = "0808";
        List<String> result = getPermutationCombination(input);
        System.out.println(result);
    }

    public static List<String> getPermutationCombination(String input) {
        List<String> result = new ArrayList<>();
        // 构建字符频率映射
        Map<Character, Integer> frequencyMap = buildFrequencyMap(input);
        char[] chars = new char[frequencyMap.size()];
        int[] counts = new int[frequencyMap.size()];
        int index = 0;

        // 将字符和频率存储到数组中
        for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
            chars[index] = entry.getKey();
            counts[index] = entry.getValue();
            index++;
        }

        // 回溯算法生成排列组合
        backtrack(chars, counts, new StringBuilder(), result, input.length());
        // 使用Set去除重复项
        Set<String> resultSet = new HashSet<>(result);
        // 将结果转换为List返回
        return new ArrayList<>(resultSet);
    }

    private static void backtrack(char[] chars, int[] counts, StringBuilder sb, List<String> result, int length) {
        // 如果已经生成了完整长度的字符串，将其加入结果列表
        if (sb.length() == length) {
            result.add(sb.toString());
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            // 跳过已经使用完的字符
            if (counts[i] == 0) continue;

            // 选择当前字符并减少其频率
            sb.append(chars[i]);
            counts[i]--;
            // 递归生成下一个字符
            backtrack(chars, counts, sb, result, length);
            // 恢复选择状态
            sb.deleteCharAt(sb.length() - 1);
            counts[i]++;
        }
    }

    private static Map<Character, Integer> buildFrequencyMap(String input) {
        Map<Character, Integer> frequencyMap = new HashMap<>();

        // 统计每个字符的频率
        for (char c : input.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        return frequencyMap;
    }
}
